package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 99. 恢复二叉搜索树
 * @date 2025/5/21 10:49
 */
public class E99 {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode prev = null;

    public void recoverTree(TreeNode root) {
        inOrder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        if (prev != null && first == null && prev.val > root.val) {
            first = prev;
        }
        if (prev != null && first != null && prev.val > root.val) {
            second = root;
        }
        prev = root;
        inOrder(root.right);
    }
}
